package com.ting.test.algorithms.二叉树;


import java.util.*;

public class 二叉树序列化 {
    public static void main(String[] args) {
//        String result = xianxu(generateRandomBST(3, 10));///n叉树 转二叉树
//        System.out.println(result);
    }

    private static Queue<Integer> cengxu(TreeNode treeNode) {
        if (null == treeNode) {
            return null;
        }
        Queue<Integer> result = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(treeNode);
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            if (poll != null) {
                result.add(poll.getVal());
            }
            if (poll.left != null) {
                result.add(poll.left.getVal());
                queue.add(poll.left);
            } else {
                result.add(null);
            }

            if (poll.right != null) {
                result.add(poll.right.getVal());
                queue.add(poll.right);
            } else {
                result.add(null);
            }
        }
        return result;

    }


    private static TreeNode cengxuni(Queue<Integer> queue) {
        Queue<TreeNode> temp = new LinkedList<>();
        TreeNode node = getNode(queue.poll());
        temp.add(node);
        while (!temp.isEmpty()) {
            TreeNode poll = temp.poll();
            poll.left = getNode(queue.poll());
            if (poll.left != null) {
                temp.add(poll.left);
            }
            poll.right = getNode(queue.poll());
            if (poll.right != null) {
                temp.add(poll.right);
            }
        }
        return node;
    }

    private static TreeNode getNode(Integer val) {
        if (val == null) {
            return null;
        } else {
            return new TreeNode(val);
        }
    }

    /**
     * 利用先序遍历，对二叉树进行序列化
     *
     * @param treeNode
     */
    private static Queue<Integer> xianxu(TreeNode treeNode) {
        if (null == treeNode) {
            return null;
        }
        Queue<Integer> result = new LinkedList<>();
        xianxuprocess(treeNode, result);
        return result;
    }

    private static void xianxuprocess(TreeNode treeNode, Queue<Integer> result) {
        if (null == treeNode) {
            result.add(null);

        }

        result.add(treeNode.getVal());
        xianxuprocess(treeNode.left, result);
        xianxuprocess(treeNode.right, result);

    }


    /**
     * 利用先序遍历，对二叉树进行逆序列化
     *
     * @param queue
     */
    private static TreeNode xianxuni(Queue<Integer> queue) {
        if (null == queue) {
            return null;
        }
        if (queue.size() == 1) {
            return new TreeNode(queue.poll());
        }

        return perNi(queue);

    }

    /**
     * @param queue
     * @return
     */
    private static TreeNode perNi(Queue<Integer> queue) {
        Integer val = queue.poll();
        if (val == null) {
            return null;
        }
        TreeNode head = new TreeNode(val);
        head.left = perNi(queue);
        head.right = perNi(queue);
        return head;
    }


    // for test
    public static TreeNode generateRandomBST(int maxLevel, int maxValue) {
        return generate(1, maxLevel, maxValue);
    }

    // for test
    public static TreeNode generate(int level, int maxLevel, int maxValue) {
        if (level > maxLevel || Math.random() < 0.5) {
            return null;
        }
        TreeNode head = new TreeNode((int) (Math.random() * maxValue));
        head.left = generate(level + 1, maxLevel, maxValue);
        head.right = generate(level + 1, maxLevel, maxValue);
        return head;
    }

}
